E%3DI T The internal extent formula for compacted tries.

Fun with Algorithms

Dynamic Z%2DFast Tries.

Layered Label Propagation A MultiResolution Coordinate%2DFree Ordering for Compressing Social Networks

HyperANF Approximating the Neighbourhood Function of Very Large Graphs on a Budget

E %3D I   T The internal extent formula for compacted tries

Proceedings of the Second International Conference on Web Search and Web Data Mining

Efficient algorithms for large%2Dscale local triangle counting.
In this article, we study the problem of approximate local triangle counting in large graphs. Namely, given a large graph G = (V, E) we want to estimate as accurately as possible the number of triangles incident to every node v ∈ V in the graph. We consider the question both for undirected and directed graphs. The problem of computing the global number of triangles in a graph has been considered before, but to our knowledge this is the first contribution that addresses the problem of approximate local triangle counting with a focus on the efficiency issues arising in massive graphs and that also considers the directed case. The distribution of the local number of triangles and the related local clustering coefficient can be used in many interesting applications. For example, we show that the measures we compute can help detect the presence of spamming activity in largescale Web graphs, as well as to provide useful features for content quality assessment in social networks. For computing the local number of triangles (undirected and directed), we propose two approximation algorithms, which are based on the idea of min-wise independent permutations [Broder et al. 1998]. Our algorithms operate in a semi-streaming fashion, using O(|V |) space in main memory and performing O(log |V |) sequential scans over the edges of the graph. The first algorithm
Proceedings of the Second International Conference on Web Search and Web Data Mining

Theory and Practise of Monotone Minimal Perfect Hashing.
Minimal perfect hash functions have been shown to be useful to compress data in several data management tasks. In particular, order-preserving minimal perfect hash functions [12] have been used to retrieve the position of a key in a given list of keys: however, the ability to preserve any given order leads to an unavoidable �(n log n) lower bound on the number of bits required to store the function. Recently, it was observed [1] that very frequently the keys to be hashed are sorted in their intrinsic (i.e., lexicographical) order. This is typically the case of dictionaries of search engines, list of URLs of web graphs, etc. We refer to this restricted version of the problem as monotone minimal perfect hashing. We analyse experimentally the data structures proposed in [1], and along our way we propose some new methods that, albeit asymptotically equivalent or worse, perform very well in practise, and provide a balance between access speed, ease of construction, and space usage. 1
Voting in social networks.
A voting system is a set of rules that a community adopts to take collective decisions. In this paper we study voting systems for a particular kind of community: electronically mediated social networks. In particular, we focus on delegative democracy (a.k.a. proxy voting) that has recently received increased interest for its ability to combine the benefits of direct and representative systems, and that seems also perfectly suited for electronically mediated social networks. In such a context, we consider a voting system in which users can only express their preference for one among the people they are explicitly connected with, and this preference can be propagated transitively, using an attenuation factor. We present this system and we study its properties. We also take into consideration the problem of missing votes, which is particularly relevant in online networks, as some recent case shows. Our experiments on real-world networks provide interesting insight into the significance and stability of the results obtained with the suggested voting system.
Monotone minimal perfect hashing searching a sorted table with O%281%29 accesses.
A minimal perfect hash function maps a set S of n keys into the set { 0, 1,..., n − 1} bijectively. Classical results state that minimal perfect hashing is possible in constant time using a structure occupying space close to the lower bound of log e bits per element. Here we consider the problem of monotone minimal perfect hashing, in which the bijection is required to preserve the lexicographical ordering of the keys. A monotone minimal perfect hash function can be seen as a very weak form of index that provides ranking just on the set S (and answers randomly outside of S). Our goal is to minimise the description size of the hash function: we show that, for a set S of n elements out of a universe of 2 w elements, O(n log log w) bits are sufficient to hash monotonically with evaluation time O(log w). Alternatively, we can get space O(n log w) bits with O(1) query time. Both of these data structures improve a straightforward construction with O(n log w) space and O(log w) query time. As a consequence, it is possible to search a sorted table with O(1) accesses to the table (using additional O(n log log w) bits). Our results are based on a structure (of independent interest) that represents a trie in a very compact way, but admits errors. As a further application of the same structure, we show how to compute the predecessor (in the sorted order of S) of an arbitrary element, using O(1) accesses in expectation and an index of O(n log w) bits, improving the trivial result of O(nw) bits. This implies an efficient index for searching a blocked memory. 1
Permuting Web Graphs.
Since the first investigations on web graph compression, it has been clear that the ordering of the nodes of the graph has a fundamental influence on the compression rate (usually expressed as the number of bits per link). The author of the LINK database [1], for instance, investigated three different approaches: an extrinsic ordering (URL ordering) and two intrinsic (or coordinate-free) orderings based on the rows of the adjacency matrix (lexicographic and Gray code); they concluded that URL ordering has many advantages in spite of a small penalty in compression. In this paper we approach this issue in a more systematic way, testing some old orderings and proposing some new ones. Our experiments are made in the WebGraph framework [2], and show that the compression technique and the structure of the graph can produce significantly different results. In particular, we show that for the transpose web graph URL ordering is significantly less effective, and that some new orderings combining host information and Gray/lexicographic orderings outperform all previous methods. In particular, in some large transposed graphs they yield the quite incredible compression rate of 1 bit per link. 1
From %22Dango%22 to %22Japanese Cakes%22 Query Reformulation Models and Patterns.
Abstract—Understanding query reformulation patterns is a key step towards next generation web search engines: it can help improving users ’ web-search experience by predicting their intent, and thus helping them to locate information more effectively. As a step in this direction, we build an accurate model for classifying user query reformulations into broad classes (generalization, specialization, error correction or parallel move), achieving 92 % accuracy. We apply the model to automatically label two large query logs, creating annotated queryflow graphs. We study the resulting reformulation patterns, finding results consistent with previous studies done on smaller manually annotated datasets, and discovering new interesting patterns, including connections between reformulation types and topical categories. Finally, applying our findings to a third query log that is publicly available for research purposes, we demonstrate that our reformulation classifier leads to improved recommendations in a query recommendation system. I.
PageRank Functional dependencies.
PageRank is defined as the stationary state of a Markov chain. The chain is obtained by perturbing the transition matrix induced by a web graph with a damping factor α that spreads uniformly part of the rank. The choice of α is eminently empirical, and in most cases the original suggestion α = 0.85 by Brin and Page is still used. In this paper, we give a mathematical analysis of PageRank when α changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of α close to 1 do not give a more meaningful ranking. Then, we give closed-form formulae for PageRank derivatives of any order, and by proving that the k-th iteration of the Power Method gives exactly the value obtained by truncating the PageRank power series at degree k, we show how to obtain an approximation of the derivatives. Finally, we view PageRank as a linear operator acting on the preference vector and show a tight connection between iterated computation and derivation. 
Pictures from Mongolia. Extracting the Top Elements from a Partially Ordered Set.
You are back from that very long, marvellous journey. You have a thousand pictures, but your friends and relatives will stand just a few dozens. Choosing is a painful process, in particular when you cannot decide between the silent vastness of that desert and the idyllic picture of that tranquil, majestic lake. We are going to help. 1 Pictures, pictures and more pictures In the summer of 2004, Paolo, Sebastiano and four more friends took part to a long journey in Mongolia, with a local guide, a driver and an old Uaz van. Five of the participants were fond of taking pictures, and Mongolia met their match: long rivers flowing through luxuriant meadows, high peaks covered with pine trees, wild horses running free, children laughing at our passage, camels in sandy deserts... On our trip back to Italy, when we were in Moscow for a short stop, we started to put together all the pictures we had been taking for three weeks and discovered that we had about six hundreds of them! (We were using mainly digital cameras and we had an old light laptop with us, so we had essentially no limit in the number of pictures we could take.) The number was scary, not only for us but also, and importantly, for all of our friends. If you ever happened to be invited to one of those just-after-holidays dinners at one of your friend’s, you know what we mean: at the end of the dinner, no doubt your friend will “propose ” to look at the pictures they have been taking during their holidays in Guatemala, and those pictures turn out to be three hundreds, and most of them about a special tree growing in the jungle, and... Yet, choosing the best representatives from a set of objects is not an easy task; even the very nature of preference is questionable, and has been largely debated by psychometricians and economists (see, e.g., [CF88]). In particular, a much argued point is whether personal preference is a transitive relation or not; even if some experiments actually prove that preference may indeed not be transitive, it is commonly agreed that intransitive preference lead to ∗ A preliminary version of this paper appeared in [BCV07].
The query%2Dflow graph model and applications.
Query logs record the queries and the actions of the users of search engines, and as such they contain valuable information about the interests, the preferences, and the behavior of the users, as well as their implicit feedback to search-engine results. Mining the wealth of information available in the query logs has many important applications including querylog analysis, user profiling and personalization, advertising, query recommendation, and more. In this paper we introduce the query-flow graph, a graph representation of the interesting knowledge about latent querying behavior. Intuitively, in the query-flow graph a directed edge from query qi to query qj means that the two queries are likely to be part of the same “search mission”. Any path over the query-flow graph may be seen as a searching behavior, whose likelihood is given by the strength of the edges along the path. The query-flow graph is an outcome of query-log mining and, at the same time, a useful tool for it. We propose a methodology that builds such a graph by mining time and textual information as well as aggregating queries from different users. Using this approach we build a real-world queryflow graph from a large-scale query log and we demonstrate its utility in concrete applications, namely, finding logical sessions, and query recommendation. We believe, however, that the usefulness of the query-flow graph goes beyond these two applications.
Temporal Evolution of the UK Web.



The number of convex permutominoes.
The number of convex permutominoes. (English summary)
A large time%2Daware web graph.
We describe the techniques developed to gather and distribute in a highly compressed, yet accessible, form a series of twelve snapshot of the.uk web domain. Ad hoc compression techniques made it possible to store the twelve snapshots using just 1.9 bits per link, with constant-time access to temporal information. Our collection makes it possible to study the temporal evolution link-based scores (e.g., PageRank), the growth of online communities, and in general time-dependent phenomena related to the link structure. 
Pictures from Mongolia %2D Partial Sorting in a Partial World.

A Deeper Investigation of PageRank as a Function of the Damping Factor.
PageRank is defined as the stationary state of a Markov chain. The chain is obtained by perturbing the transition matrix induced by a web graph with a damping factor α that spreads uniformly part of the rank. The choice of α is eminently empirical, and in most cases the original suggestion α = 0.85 by Brin and Page is still used. In this paper, we give a mathematical analysis of PageRank when α changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of α close to 1 do not give a more meaningful ranking. Then, we give closed-form formulae for PageRank derivatives of any order, and by proving that the k-th iteration of the Power Method gives exactly the PageRank value obtained using a Maclaurin polynomial of degree k, we show how to obtain an approximation of the derivatives. Finally, we view PageRank as a linear operator acting on the preference vector and show a tight connection between iterated computation and derivation. 1
Efficient Optimally Lazy Algorithms for Minimal%2DInterval Semantics

Generic Damping Functions for Propagating Importance in Link%2DBased Ranking.
Generic damping functions for propagating importance in link-based ranking. (English summary) Internet Math. 3 (2006), no. 4, 445–478. Summary: “This paper introduces a family of link-based ranking algorithms that propagate page importance through links. The algorithms include a damping function that decreases with distance, thus a direct link implies greater endorsement than a link via a longer path. PageRank is the most widely known ranking function of this family. “The main objective of this paper is to determine whether this family of ranking techniques is of some interest per se and how different choices for the damping function affect rank quality and convergence speed. Even though our results suggest that PageRank can be approximated with other, more simple forms of rankings that may be computed more efficiently, our focus is more speculative in nature, given that it aims at separating the kernel of PageRank, that is, link-based importance propagation, from the way propagation decays over paths. “We focus on three damping functions that have, respectively, linear, exponential, and hyperbolic decay on the lengths of the paths. The exponential decay corresponds to PageRank, and the
Generalizing PageRank damping functions for link%2Dbased ranking algorithms.
This paper introduces a family of link-based ranking algorithms that propagate page importance through links. In these algorithms there is a damping function that decreases with distance, so a direct link implies more endorsement than a link through a long path. PageRank is the most widely known ranking function of this family. The main objective of this paper is to determine whether this family of ranking techniques has some interest per se, and how different choices for the damping function impact on rank quality and on convergence speed. Even though our results suggest that Page-Rank can be approximated with other simpler forms of rankings that may be computed more efficiently, our focus is of more speculative nature, in that it aims at separating the kernel of PageRank, that is, link-based importance propagation, from the way propagation decays over paths. We focus on three damping functions, having linear, exponential, and hyperbolic decay on the lengths of the paths. The exponential decay corresponds to PageRank, and the other functions are new. Our presentation includes algorithms, analysis, comparisons and experiments that study their behavior under different parameters in real Web graph data. Among other results, we show how to calculate a linear approximation that induces a page ordering that is almost identical to Page-Rank’s using a fixed small number of iterations; comparisons were performed using Kendall’s τ on large domain datasets.
Efficient Lazy Algorithms for Minimal%2DInterval Semantics.

MG4J at TREC 2006.

MG4J at TREC 2006.

Graph fibrations%2C graph isomorphism%2C and PageRank.
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the values that PageRank can assume. Using our results, we show that a recently defined class of graphs that admit a polynomial-time isomorphism algorithm based on the computation of PageRank is really a subclass of fibration-prime graphs, which possess simple, entirely discrete polynomial-time isomorphism algorithms based on classical techniques for graph isomorphism. We discuss efficiency issues in the implementation of such algorithms for the particular case of web graphs, in which O(n) space occupancy (where n is the number of nodes) may be acceptable, but O(m) is not (where m is the number of arcs). 1
Traps and Pitfalls of Topic%2DBiased PageRank.
We discuss a number of issues in the definition, computation and comparison of PageRank values that have been addressed sparsely in the literature, often with contradictory approaches. We study the difference between weakly and strongly preferential PageRank, which patch the dangling nodes with different distributions, extending analytical formulae known for the strongly preferential case, and corroborating our results with experiments on a snapshot of 100 millions of pages of the.uk domain. The experiments show that the two PageRank versions are poorly correlated, and results about each one cannot be blindly applied to the other; moreover, our computations highlight some new concerns about the usage of exchange-based correlation indices (such as Kendall’s τ) on approximated rankings. 1
Graph fibrations%2C graph isomorphism%2C and PageRank.
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the values that PageRank can assume. Using our results, we show that a recently defined class of graphs that admit a polynomial-time isomorphism algorithm based on the computation of PageRank is really a subclass of fibration-prime graphs, which possess simple, entirely discrete polynomial-time isomorphism algorithms based on classical techniques for graph isomorphism. We discuss efficiency issues in the implementation of such algorithms for the particular case of web graphs, in which O(n) space occupancy (where n is the number of nodes) may be acceptable, but O(m) is not (where m is the number of arcs). 1
A reference collection for web spam.
We describe the WEBSPAM-UK2006 collection, a large set of Web pages that have been manually annotated with labels indicating if the hosts are include Web spam aspects or not. This is the first publicly available Web spam collection that includes page contents and links, and that has been labelled by a large and diverse set of judges. 1
Compressed Perfect Embedded Skip Lists for Quick Inverted%2DIndex Lookups.
Large inverted indices are by now common in the construction of web-scale search engines. For faster access, inverted indices are indexed internally so that it is possible to skip quickly over unnecessary documents. The classical approach to skipping dictates that a skip should be positioned every √ f document pointers, where f is the overall number of documents where the term appears. We argue that due to the growing size of the web more refined techniques are necessary, and describe how to embed a compressed perfect skip list in an inverted list. We provide statistical models that explain the empirical distribution of the skip data we observe in our experiments, and use them to devise good compression techniques that allow us to limit the waste in space, so that the resulting data structure increases the overall index size by just a few percents, still making it possible to index pointers with a rather fine granularity. 1
MG4J at TREC 2005.
MG4J participated in two tracks of TREC 2005 --- the ad hoc task and the efficiency  task of the Terabyte Track (find all the relevant documents with high precision from 25.2  million pages from the .gov domain). It was the first time the MG4J group participated  to TREC, and we concentrated our efforts on the ad hoc task, using a combination of  techniques based on a new multi-index minimal-interval semantics and PageRank.
PageRank as a function of the damping factor.
PageRank is defined as the stationary state of a Markov chain. The chain is obtained by perturbing the transition matrix induced by a web graph with a damping factor # that spreads uniformly part of the rank. The choice of # is eminently empirical, and in most cases the original suggestion # = 0.85 by Brin and Page is still used. Recently, however, the behaviour of PageRank with respect to changes in # was discovered to be useful in link-spam detection [21]. Moreover, an analytical justification of the value chosen for # is still missing. In this paper, we give the first mathematical analysis of PageRank when # changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of # close to 1 do not give a more meaningful ranking. Then, we give closed-form formulae for PageRank derivatives of any order, and an extension of the Power Method that approximates them with convergence  O        for the k-th derivative. Finally, we show a tight connection between iterated computation and analytical behaviour by proving that the k-th iteration of the Power Method gives exactly the PageRank value obtained using a Maclaurin polynomial of degree k. The latter result paves the way towards the application of analytical methods to the study of PageRank.
TotalRank ranking without damping.
PageRank is defined as the stationary state of a Markov chain obtained by perturbing the transition matrix of a web graph with a damping factor # that spreads part of the rank. The choice of # is eminently empirical, but most applications use # = 0.85; nonetheless, the selection of # is critical, and some believe that link farms may use this choice adversarially. Recent results [1] prove that the PageRank of a page is a rational function of #, and that this function can be approximated quite efficiently: this fact can be used to define a new form of ranking, TotalRank, that averages PageRanks over all possible #&#039;s. We show how this rank can be computed efficiently, and provide some preliminary experimental results on its quality and comparisons with PageRank.
The language observatory project %28LOP%29.
The first part of the paper provides a brief description of the Language Observatory Project (LOP) and highlights the major technical difficulties to be challenged. The latter part gives how we responded to these difficulties by adopting UbiCrawler as a data collecting engine for the project. An interactive collaboration between the two groups is producing quite satisfactory results.
Paradoxical Effects in PageRank Incremental Computations.
Deciding which kind of visiting strategy accumulates high-quality pages more quickly is one of the most often debated issues in the design of web crawlers. This paper proposes a related, and previously overlooked, measure of effectivity for crawl strategies: whether the graph obtained after a partial visit is in some sense representative of the underlying web graph as far as the computation of PageRank is concerned. More precisely, we are interested in determining how rapidly the computation of PageRank over the visited subgraph yields rankings that agree with the ones computed in the complete graph; ranks are compared using Kendall’s τ. We describe a number of large-scale experiments that show the following paradoxical effect: visits that gather PageRank more quickly (e.g., highest-quality first) are also those that tend to miscalculate PageRank. Finally, we perform the same kind of experimental analysis on some synthetic random graphs, generated using well-known web-graph models: the results are almost opposite to those obtained on real web graphs. 1
Codes for the World Wide Web.
To find out what kind of design structures programmers really use, we need to examine a wide variety of programs. Unfortunately most program source code is proprietary and is unavailable for analysis. The World Wide Web (Web) potentially can provide a rich source of programs for study. The freely available code on the Web, if in sufficient quality and quantity, can provide a window into software design as it is practiced today. In a preliminary study of source code availability on the Web, we estimate that 4% of URLs contain object-oriented source code, and 9% of URLs contain executable code --- either binary or class files. This represents an enormous resource for program analysis. We can, with some risk of inaccuracy, conservatively project our sampling results to the entire Web. Our estimate is that the Web contains at least 3.4 million files containing either Java, C++, or Perl source code, 20.3 million files containing C source code, and 8.7 million files containing executable code.  Keywords: Design, source code analysis, World Wide Web estimation, code on the World Wide Web.  1. 
Mutable strings in Java design

The WebGraph Framework II Codes For The World%2DWide Web.
A fundamental observation about compression of the web graph was made in the  construction of the LINK database [11]: if we order URLs lexicographically, ordered  successor lists tend to have small gaps, which can be coded using standard methods  from full-text index construction. In this paper, we propose  codes, a family of simple  at codes that are targeted at those gaps, and we give the rst thorough mathematical  comparative analysis of several codes against power-law distributions with small  exponent, which are common for such gaps in web graphs.
WebGraph things you thought you could not do with Java%26trade%3B.

Do Your Worst to Make the Best Paradoxical Effects in PageRank Incremental Computations.
Abstract Deciding which kind of visit accumulates high-quality pages more quickly is one of the most often debatedissue in the design of web crawlers. It is known that breadth-first visits work well, as they tend to discover pages with high PageRank early on in the crawl. Indeed, this visit order is much better than depth first, which is inturn even worse than a random visit; nevertheless, breadth-first can be superseded using an omniscient visit that chooses, at every step, the node of highest PageRank in the frontier.This paper discusses a related, and previously overlooked, measure of effectivity for crawl strategies: whether the graph obtained after a partial visit is in some sense representative of the underlying web graph as far asthe computation of PageRank is concerned. More precisely, we are interested in determining how rapidly the computation of PageRank over the visited subgraph yields relative ranks that agree with the ones the nodes havein the complete graph; ranks are compared using Kendall&#039;s #.We describe a number of large-scale experiments that show the following paradoxical effect: visits that gather PageRank more quickly (e.g., highest-quality-first) are also those that tend to miscalculate PageRank. Finally, weperform the same kind of experimental analysis on some synthetic random graphs, generated using well-known web-graph models: the results are almost opposite to those obtained on real web graphs. 1 Introduction The search for the better crawling strategy (i.e., a strategy that gathers early pages of high quality) is by now analmost old research topic (see, e.g., [8]). Being able to collect quickly high-quality pages is one of the major design goals of a crawler; this issue is particularly important, because, as noted in [11], even after crawling well over abillion pages, the number of uncrawled pages still far exceeds the number of crawled pages.1 Usually, a basic measure of quality is PageRank [28], in one of its many variants. Hence, as a first step we cancompare two strategies by looking at how fast the cumulative PageRank (i.e., the sum of the PageRanks of all the visited pages up to a certain point) grows over time. Of course, this comparison can only be performed after the endof the crawl, because one needs the whole graph to compute PageRank.
Do Your Worst to Make the Best Paradoxical Effects in PageRank Incremental Computations.
Abstract Deciding which kind of visit accumulates high-quality pages more quickly is one of the most often debatedissue in the design of web crawlers. It is known that breadth-first visits work well, as they tend to discover pages with high PageRank early on in the crawl. Indeed, this visit order is much better than depth first, which is inturn even worse than a random visit; nevertheless, breadth-first can be superseded using an omniscient visit that chooses, at every step, the node of highest PageRank in the frontier.This paper discusses a related, and previously overlooked, measure of effectivity for crawl strategies: whether the graph obtained after a partial visit is in some sense representative of the underlying web graph as far asthe computation of PageRank is concerned. More precisely, we are interested in determining how rapidly the computation of PageRank over the visited subgraph yields relative ranks that agree with the ones the nodes havein the complete graph; ranks are compared using Kendall&#039;s #.We describe a number of large-scale experiments that show the following paradoxical effect: visits that gather PageRank more quickly (e.g., highest-quality-first) are also those that tend to miscalculate PageRank. Finally, weperform the same kind of experimental analysis on some synthetic random graphs, generated using well-known web-graph models: the results are almost opposite to those obtained on real web graphs. 1 Introduction The search for the better crawling strategy (i.e., a strategy that gathers early pages of high quality) is by now analmost old research topic (see, e.g., [8]). Being able to collect quickly high-quality pages is one of the major design goals of a crawler; this issue is particularly important, because, as noted in [11], even after crawling well over abillion pages, the number of uncrawled pages still far exceeds the number of crawled pages.1 Usually, a basic measure of quality is PageRank [28], in one of its many variants. Hence, as a first step we cancompare two strategies by looking at how fast the cumulative PageRank (i.e., the sum of the PageRanks of all the visited pages up to a certain point) grows over time. Of course, this comparison can only be performed after the endof the crawl, because one needs the whole graph to compute PageRank.
The webgraph framework I compression techniques.
Studying web graphs is often dicult due to their large size. Recently, several proposals  have been published about various techniques that allow to store a web graph in memory in  a limited space, exploiting the inner redundancies of the web. The WebGraph framework  is a suite of codes, algorithms and tools that aims at making it easy to manipulate large  web graphs. This papers presents the compression techniques used in WebGraph, which  are centred around referentiation and intervalisation (which in turn are dual to each other).
Rethinking Java strings.
The Java string classes, String and StringBuffer, lie at the extremes of a spectrum (immutable,  reference-based and mutable, content-based). Motivated by data-intensive text applications, we propose a  new string class, MutableString, which tries to embody the best of both approaches.
Compact Approximation of Lattice Functions with Applications to Large%2DAlphabet Text Search
We propose a very simple randomised data structure that stores an approximation from above  of a lattice-valued function. Computing the function value requires a constant number of steps, and  the error probability can be balanced with space usage, much like in Bloom filters. The structure  is particularly well suited for functions that are bottom on most of their domain. We then show  how to use our methods to store in a compact way the bad-character shift function for variants of  the Boyer-Moore text search algorithms. As a result, we obtain practical implementations of these  algorithms that can be used with large alphabets, such as Unicode collation elements, with a small  setup time.
Lower bounds for sense of direction in regular graphs.

Lower bounds for weak sense of direction.
A graph with n vertices and maximum degree # cannot be given weak sense of direction  using less than # colours. It is known that n colours are always sufficient, but it has been  conjectured that just #+1 are really needed. On the contrary, we show that for sufficiently  large n there are graphs requiring #    #(n/ log n) colours. We also give simple examples  of small graphs requiring #+ 2 colours, which have been verified mechanically.
Holographic Trees.

Fibrations of graphs.
A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods,  much in the same way a covering projection is a local isomorphism of neighbourhoods. This  paper develops systematically the theory of graph fibrations, emphasizing in particular those  results that recently found application in the theory of distributed systems.  Keywords: graph fibrations, graph coverings, graph factorizations.  Contents  1 Introduction 2 2 Definitions and basic properties 3 2.1 Graph-theoretical definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Fibrations and coverings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Groups, fibrations and automorphisms . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Some properties of fibrations between finite graphs . . . . . . . . . . . . . . . . . 9 2.5 An application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Universal fibrations and coverings 11 3.1 Univer...
Universal dynamic synchronous self%2Dstabilization.
We prove the existence of a &#034;universal&#034; synchronous self-stabilizing protocol, that is, a protocol that allows a distributed system to stabilize to a desired nonreactive behaviour (as long as a protocol stabilizing to that behaviour exists). Previous proposals required drastic increases in asymmetry and knowledge to work, whereas our protocol does not use any additional knowledge, and does not require more symmetry-breaking conditions than available; thus, it is also stabilizing with respect to dynamic changes in the topology. We prove an optimal quiescence time n  +  D for a synchronous network of n processors and diameter D; the protocol can be made finite state with a negligible loss in quiescence time. Moreover, an optimal D  +  1 protocol is given for the case of unique identifiers. As a consequence, we provide an effective proof technique that allows to show whether self-stabilization to a certain behaviour is possible under a wide range of models.  Keywords: self-stabilization, anonymous networks, graph fibrations, synchronous systems. 1 
Universal Homogeneous Graph%2DLike Structures And Domains.

Measuring with jugs.
We study the jug problem in its most general form: given a set of jugs of fixed capacities, find out which quantities are measurable, and provide upper and lower bounds on the number of steps necessary for measurements.

An Effective Characterization of Computability in Anonymous Networks.
We provide effective (i.e., recursive) characterizations of the relations  that can be computed on networks where all processors use the same algorithm,  start from the same state, and know at least a bound on the network size. Three  activation models are considered (synchronous, asynchronous, interleaved).

delta%2DApproximable Functions.
In this paper we study several notions of approximability of functions in the  framework of the BSS model. Denoting with #  #  M  the function computed by a  BSS machine M when its comparisons are against  -#  rather than 0, we study  classes of functions f for which #  #  M  #  f in some sense (pointwise, uniformly,  etc.). The main equivalence results show that this notion coincides with Type 2  computability when the convergence speed is recursively bounded. Finally, we  study the possibility of extending these results to computations over Archimedean  fields.  1 
More Lower Bounds for Weak Sense of Direction The Case of Regular Graphs.
A graph G with n vertices and maximum degree # G cannot be given weak sense of direction using less than # G colours. It is known that n colours are always sufficient, and it was conjectured that just # G  +  1 are really needed, that is, one more colour is sufficient. Nonetheless, it has just been shown [2] that for sufficiently large n there are graphs requiring #(n/ log n) more colours than # G . In this paper, using recent results in asymptotic graph enumeration, we show not only that (somehow surprisingly) the same bound holds for regular graphs, but also that it can be improved to #(n log log n/ log n). We also show that #  #  d G # log log d G  #  colours are necessary, where d G is the degree of G. 1 
Lower bounds for %28weak%29 sense of direction.
A graph with n vertices and maximum degree # cannot be given weak sense of direction  using less than # colours. It is known that n colours are always sufficient, but it has been  conjectured that just #+1 are really needed. On the contrary, we show that for sufficiently  large n there are graphs requiring #    #(n/ log n) colours. We also give simple examples  of small graphs requiring #+ 2 colours, which have been verified mechanically.
Coverings that preserve sense of direction.
Sense of direction is a property of labelled networks (i.e., arc-coloured graphs) that allows one to assign coherently local identifiers to other processors on the basis of the route followed by incoming messages. We prove that (weak) sense of direction is preserved by the construction of regular coverings (i.e., coverings induced by voltage assignments in a group) whose voltage assignment depends only on colours. Moreover, this construction preserves minimality.  Key words: distributed systems, interconnection networks, sense of direction, graph coverings. 1 Introduction  Sense of direction [7] is a property of global consistency of the colouring of a network that can be used to reduce the complexity of distributed algorithms [6]. Although there are polynomial algorithms for checking whether a given coloured graph has (weak) sense of direction [4], the polynomial bounds are rather high, and, moreover, there are no results (besides the obvious membership to NP) about finding a colourin...
The Turing closure of an Archimedean field.
A BSS machine is #-uniform if it does not use exact tests; such machines are equivalent (modulo parameters) to Type 2 Turing machines. We define a notion of closure related to Turing machines for archimedean fields, and show that such fields admit nontrivial #-uniformly decidable sets iff they are not Turing closed. Then, the partially ordered set of Turing closed fields is proved isomorphic to the ideal completion of unsolvability degrees. 1 Introduction  In a previous paper [2], the authors have introduced a version of the BSS model of computability [1] in which exact tests are not allowed. Essentially, a BSS machine is #-uniform  iff its halting set and computed function do not change when the test for equality with 0 is replaced with a test for membership to an arbitrary ball around 0. A set is #-uniformly  semi-decidable iff it is the halting set of a #-uniform BSS machine; as it turns out, such sets are always open. There is a strict relation between #-uniform computability and r...
Computing Anonymously with Arbitrary Knowledge.
We provide characterizations of the relations that can be computed with arbitrary knowledge on networks where all processors use the same algorithm and start from the same state (in particular, we do not assume that a bound on the network size is known). Three activation models are considered (synchronous, asynchronous, interleaved) . 1 Introduction  The question concerning which problems can be solved by a distributed system when all processors use the same algorithm and start from the same state has a long story: it was firstly formulated by Angluin [1], who investigated the problem of establishing a &#034;center&#034;. She was the first to realize the connection with the theory of graph coverings, which was going to provide, in particular with the work of Yamashita and Kameda [11], several characterization for problems that are solvable under certain topological constraints. Further investigation led to the classification of computable functions [11, 10, 3, 9], and allowed to eliminate severa...
Complexity of Deciding Sense of Direction.
In this paper we prove that deciding whether a distributed system (represented as a coloured digraph with n nodes) has weak sense of direction is in AC¹ (using n^6 processors). Moreover, we show that deciding sense of direction is in P. Our algorithms can also be used in order to decide in AC¹   whether a coloured graph is a Cayley colour graph.  
Equality is a Jump.

The Turing Closure of an Archimedean Field.
A BSS machine is #-uniform if it does not use exact tests; such machines are equivalent (modulo parameters) to Type 2 Turing machines. We define a notion of closure related to Turing machines for archimedean fields, and show that such fields admit nontrivial #-uniformly decidable sets iff they are not Turing closed. Then, the partially ordered set of Turing closed fields is proved isomorphic to the ideal completion of unsolvability degrees. 1 Introduction  In a previous paper [2], the authors have introduced a version of the BSS model of computability [1] in which exact tests are not allowed. Essentially, a BSS machine is #-uniform  iff its halting set and computed function do not change when the test for equality with 0 is replaced with a test for membership to an arbitrary ball around 0. A set is #-uniformly  semi-decidable iff it is the halting set of a #-uniform BSS machine; as it turns out, such sets are always open. There is a strict relation between #-uniform computability and r...
delta%2DUniform BSS Machines.
A #-uniform BSS machine is a standard BSS machine which does not rely on exact equality tests. We prove that, for any archimedean field R, a set is #-uniformly semidecidable iff it is open and semi-decidable by a BSS machine which is locally time bounded; we also prove that the local time bound is nontrivial. This entails a number of results about BSS machines, in particular the existence of decidable sets whose interior (closure) is not even semi-decidable without adding constants. Finally, we show that the sets semidecidable by Turing machines are the sets semi-decidable by #-uniform machines with coefficients in Q or T, the field of Turing computable numbers. 1 Introduction  The problem of deciding subsets of reals has given rise to two complementary approaches: following the tradition of Turing, Type 2 recursion theory [18] studies the sets decided by generalized Turing machines whose input tape contains a representation of a real number; on the other hand, the BSS model [1] consid...
Computing Vector Functions on Anonymous Networks.
We characterize exactly the vector functions f : #  n  #  #  n  computable by several classes of anonymous networks. We study both undirectional and bidirectional networks, (partially) wireless networks, and two different processor activation models (synchronous and asynchronous). We also identify the rigidity conditions under which a network can compute every function.  Keywords: Anonymous networks, wireless networks, distributed computation, graphs, fibrations 1 Introduction  Given a network, we can legitimately ask which functions can the network compute distributely. More precisely, given a domain of values # and a function f : #  n  #  #  n  , where n is the number of processors of the network, we can ask whether the network (or any network out of a certain class) can compute f . The question is of course meaningful only if the network is anonymous, i.e., if the processors do not possess unique identifiers. Other problems, such as the election problem, have been studied on such ne...
Computing Vector Functions on Anonymous Networks.
We characterize exactly the vector functions f : #  n  #  #  n  computable by several classes of anonymous networks. We study both undirectional and bidirectional networks, (partially) wireless networks, and two different processor activation models (synchronous and asynchronous). We also identify the rigidity conditions under which a network can compute every function.  Keywords: Anonymous networks, wireless networks, distributed computation, graphs, fibrations 1 Introduction  Given a network, we can legitimately ask which functions can the network compute distributely. More precisely, given a domain of values # and a function f : #  n  #  #  n  , where n is the number of processors of the network, we can ask whether the network (or any network out of a certain class) can compute f . The question is of course meaningful only if the network is anonymous, i.e., if the processors do not possess unique identifiers. Other problems, such as the election problem, have been studied on such ne...
Self%2Dstabilizing universal algorithms.
. We prove the existence of a &#034;universal&#034; self-stabilizing algorithm, i.e., an algorithm which allows to stabilize a distributed system to a desired behaviour (as long as an algorithm stabilizing to that behaviour exists). Previous proposals required drastic increases in asymmetry and knowledge in order to work, while our algorithm does not use any additional knowledge, and does not require more symmetry-breaking conditions than available; thus, it is also stabilizing with respect to changes in the topology and in the identifiers assigned to each processor. We prove a tight quiescence time n  +  # for a synchronous network of n processors and diameter #. The algorithm can be made finite state with a negligible multiplicative loss. If the activation is asynchronous, we propose an algorithm with O(#n  2  ) quiescence time. Our results are true for a wide variety of sharedmemory models, including unidirectional, wireless and uniform networks. 1 Introduction  A system is self-stabilizing i...
Minimal Sense of Direction and Decision Problems for Cayley Graphs.
Sense of direction is a property of the labelling of (possibly anonymous) networks which allows to assign coherently local identifiers to other processors on the basis of the route followed by incoming messages. A graph has minimal sense of direction whenever it has sense of direction and the number of colours equals its maximum outdegree. We prove that an outregular digraph with minimal weak sense of direction is a Cayley colour graph (in the general sense, i.e., we do not require connectedness). Since Cayley colour graphs are known to possess minimal transitive sense of direction, we obtain a characterization of outregular graphs with minimal (weak,transitive) sense of direction. As a consequence, deciding whether a coloured graph is a Cayley colour graph reduces to deciding whether it has weak sense of direction, which can be done in AC¹.
Symmetry Breaking in Anonymous Networks Characterizations.
We characterize exactly the cases in which it is possible to elect a leader in an anonymous network of processors by a deterministic algorithm, and we show that for every network there is a weak election algorithm (i.e., if election is impossible all processors detect this fact in a distributed way). 1 Introduction We consider the problem of electing a leader in an anonymous network of processors. More precisely our model is that of a directed graph, with vertices corresponding to processors, and arcs to communication links (we freely interchange symmetric digraphs and undirected graphs). We make no assumption on the structure of the network: selfloops and parallel arcs are allowed. In particular, processors are anonymous: they do not have unique identifiers. We consider both synchronous and asynchronous processor activation models, and models with and without &#034;port awareness&#034; (local names for outgoing and/or for incoming arcs). We consider both unidirectional and bidirectional links. ...
Good Fibrations and Other Construction Which Preserve Sense of Direction.

Maximal Chains and Antichains in Strongly Noetherian Semiorders.

On the Complexity of Deciding Sense of Direction.
In this paper we prove that deciding whether a distributed system (represented as a coloured digraph with n nodes) has weak sense of direction is in AC¹ (using n^6 processors). Moreover, we show that deciding sense of direction is in P. Our algorithms can also be used in order to decide in AC¹   whether a coloured graph is a Cayley colour graph.  
